package ms;

public class Q1 {
    static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.value = val;
        }
    }

    public static TreeNode nextInorderNode(TreeNode root, TreeNode cur) {
        if (cur == null)
            return null;
        TreeNode  nextNode = null;
        //If the given node has a right child
        TreeNode right = cur.right;
        if (right != null) {
            //find the most left child of its right subtree
            while (right.left != null) {
                right = right.left;
            }
            return right;
        }else{
            //the given node has no right child
            // search the path from root to cur using property of BST
            // and record the nearest node whose value is larger than cur
            TreeNode head = root;
            while(head != cur){
                if(head.value > cur.value){
                    nextNode = head;
                }
                if (head.value < cur.value) {
                    head = head.right;
                } else {
                    head = head.left;
                }
            }
        }
        return nextNode;
    }

    public static void main(String[] args) {
        TreeNode root  = new TreeNode(11);
        TreeNode a = new TreeNode(9);
        TreeNode b = new TreeNode(14);
        TreeNode c = new TreeNode(7);
        TreeNode d = new TreeNode(12);
        TreeNode e = new TreeNode(15);
        TreeNode f = new TreeNode(10);
        TreeNode g = new TreeNode(6);
        TreeNode h = new TreeNode(8);
        root.left = a;
        root.right = b;
        b.left = d;
        b.right = e;
        a.left = c;
        a.right = f;
        c.right = g;
        c.right = h;

        TreeNode ans1  = nextInorderNode(root,b);
        if(ans1 != null){
        System.out.println(ans1.value);}
        else{
            System.out.println("No next node, the searched node is the largest node in the BST");
        }

        TreeNode ans2  = nextInorderNode(root,root);
        if(ans2 != null){
        System.out.println(ans2.value);}
        else{
            System.out.println("No next node, the searched node is the largest node in the BST");
        }

        TreeNode ans3  = nextInorderNode(root,c);
        if(ans3 != null){
        System.out.println(ans3.value);}
        else{
            System.out.println("No next node, the searched node is the largest node in the BST");
        }

//        System.out.println(this.getClass().getInterfaces());
    }

}
